import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution1 {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode tmp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tmp;
    }
}

class Solution2 {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode tmp = head.next.next;
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = swapPairs(tmp);
        return newHead;
    }
}

class Solution3 {
    public double myPow(double x, int n) {
        if(n < 0) return myPow(1/x,-n);
        if(n == 1) return x;
        if(n == 0) return 1;


        if(n % 2 == 1) {
            double k = myPow(x,n/2);
            return x * k* k;
        }
        else {
            double k = myPow(x,n/2);
            return k*k;
        }
    }
}

   class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution4 {
    public boolean evaluateTree(TreeNode root) {
        if(root.val == 1) return true;
        else if(root.val == 0) return false;
        else if(root.val == 2) return evaluateTree(root.left) || evaluateTree(root.right);
        else return evaluateTree(root.left) && evaluateTree(root.right);
    }
}

class Solution {
    public int sumNumbers(TreeNode root) {
       return dfs(root,0);
    }

    public int dfs(TreeNode root, int n) {
        n = n*10 + root.val;
        if(root.left == null && root.right == null) return n;

        int left = 0, right = 0;
        if(root.left!=null) {
            left = dfs(root.left,n);
        }
        if(root.right!=null){
            right = dfs(root.right,n);
        }
        return left + right;
    }
}


public class Test {
}
